package _1_初级._1_1_数组;

//import org.junit.jupiter.api.Test;

import com.alibaba.fastjson.JSON;
import org.junit.jupiter.api.Test;

import java.util.*;

public class _136_只出现一次的数字 {
    /**
     * 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
     *
     * 说明：
     *
     * 你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
     *
     * 示例 1:
     *
     * 输入: [2,2,1]
     * 输出: 1
     *
     * 示例 2:
     *
     * 输入: [4,1,2,1,2]
     * 输出: 4
     *
     */

    //解法一：数组
    public static int singleNumber1(int[] nums) {

        int[] tempArray = nums;
        boolean isEquals;

        for(int i = 0; i < nums.length; i++){
            isEquals = false;
            for(int j = 0; j < tempArray.length; j++){
                if(i == j){
                    continue;
                }
                if(nums[i] == tempArray[j]){
                    isEquals = true;
                    break;
                }
            }
            if (!isEquals){
                return nums[i];
            }
        }

        return -1;
    }

    //解法二：List
    public static int singleNumber2(int[] nums){

        List<Integer> list = new ArrayList<>();

        for (int num : nums) {
            if (!list.contains(num)) {
                list.add(num);
            } else {
                //根据值删除元素
                list.remove((Object)num);
            }
        }
        return list.get(0);

    }

    //解法三：Map
    public static int singleNumber3(int[] nums) {

        Map<Integer,Integer> map = new HashMap<>();

        for(int num : nums) {
            //判断map中是否包含key值, 包含返回该key值对应的value值;否则返回defaultValue值.
            map.put(num, map.getOrDefault(num,0) + 1);
        }
        for(int num : nums){
            if(map.get(num) == 1){
                return map.get(num);
            }
        }

        return 0;
    }

    //解法四：Set
    //2∗(a+b+c)−(a+a+b+b+c)=c
    public static int singleNumber4(int[] nums) {
        int sumOfSet = 0, sumOfNums = 0;
        Set<Integer> set = new HashSet();

        for (int num : nums) {
            if (!set.contains(num)) {
                set.add(num);
                sumOfSet += num;
            }
            sumOfNums += num;
        }
        return 2 * sumOfSet - sumOfNums;
    }



    //解法五：异或
    public static int singleNumber5(int[] nums){

        int result = 0;

        for(int temp : nums){
            result ^= temp;
        }

        return result;
    }


        public static void main(String[] args) {
        int[] nums1 = new int[]{2,2,1};
        int[] nums2 = new int[]{4,1,2,1,2};
        int[] nums3 = new int[]{4,1,2,2,4};
        System.out.println(singleNumber4(nums1));
    }


}
